#include <vector>
#include <queue>
#include <iostream>
using namespace std;
class Solution
{
public:
    vector<int> findMinHeightTrees(int n, vector<vector<int>> &edges)
    {
        if(edges.empty()){
            return vector<int>(1,0);
        }
        vector<bool> visited(n, false);
        queue<int> nodes;
        vector<vector<int>> node2edges(n, vector<int>());
        int size = edges.size();
        for (int i = 0; i < size; i++)
        {
            vector<int> edge = edges[i];
            node2edges[edge[0]].push_back(edge[1]);
            node2edges[edge[1]].push_back(edge[0]);
        }
        int visitedCount = 0;
        for (int i = 0; i < n; i++)
        {
            if (node2edges[i].size() == 1)
            {
                nodes.push(i);
                visited[i] = true;
                visitedCount++;
            }
        }
        vector<int> ans;
        while (visitedCount < n)
        {
            int t = nodes.size();
            for (int i = 0; i < t; i++)
            {
                int node = nodes.front();
                nodes.pop();
                vector<int> to = node2edges[node];
                int s = to.size();
                for (int i = 0; i < s; i++)
                {
                    if (!visited[to[i]])
                    {
                        nodes.push(to[i]);
                        visited[to[i]] = true;
                        visitedCount++;
                    }
                }
            }
        }
        while (!nodes.empty())
        {
            ans.push_back(nodes.front());
            nodes.pop();
        }
        return ans;
    }
};
int main(int argc, char const *argv[])
{
    int n = 7;
    vector<vector<int>> edges;
    edges.push_back({0, 1});
    // edges.push_back({3, 1});
    // edges.push_back({3, 2});
    // edges.push_back({3, 4});
    // edges.push_back({5, 4});
    Solution s;
    vector<int> res = s.findMinHeightTrees(n, edges);
    for (int i = 0; i < res.size(); i++)
    {
        cout << res[i] << endl;
    }

    return 0;
}
